package zjl.util;

import zjl.graph.BaseWeightedElement;

import java.util.LinkedList;
import java.util.List;

public class QYPriorityQueue<E extends BaseWeightedElement> {

    private List<E> elementList = new LinkedList<E>();

    private int limitSize = -1;

    private boolean isIncremental = false;

    public QYPriorityQueue() { }

    public QYPriorityQueue(int limitSize, boolean isIncremental) {
        this.limitSize = limitSize;
        this.isIncremental = isIncremental;
    }

    public boolean isEmpty() {
        return this.elementList.isEmpty();
    }

    public int size() {
        return this.elementList.size();
    }

    public void offer(E element) {
        this.elementList.add(binaryLocatePosition(element.getWeight(), isIncremental), element);

        if (limitSize > 0 && elementList.size() > limitSize) {
            int sizeOfResults = elementList.size();
            this.elementList.remove(sizeOfResults - 1);
        }
    }

    public E poll() {
        E ret = this.get(0);
        this.elementList.remove(ret);

        return ret;
    }

    public E get(int index) {
        if (index >= elementList.size()) {
            System.err.println("The result: " + index + " does not exist.");
        }

        return this.elementList.get(index);
    }

    // Binary search is exploited to find the right position of the new element.
    private int binaryLocatePosition(double weight, boolean isIncremental) {
        int mid = 0;
        int low = 0;
        int high = elementList.size() - 1;

        while (low <= high) {
            mid = (low + high) / 2;

            if (elementList.get(mid).getWeight() == weight)
                return mid + 1;

            if (isIncremental) {
                if (elementList.get(mid).getWeight() < weight) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if (elementList.get(mid).getWeight() > weight) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }

        return low;
    }

    @Override
    public String toString() {
        return this.elementList.toString();
    }
}
